// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

// 你可以假设数组中无重复元素。

// 示例 1:

// 输入: [1,3,5,6], 5
// 输出: 2
// 示例 2:

// 输入: [1,3,5,6], 2
// 输出: 1
// 示例 3:

// 输入: [1,3,5,6], 7
// 输出: 4
// 示例 4:

// 输入: [1,3,5,6], 0
// 输出: 0

#include <vector>

using namespace std;

/* 二分查找
时间复杂度：O(logN)
空间复杂度：O(1)
*/
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int lhs = 0;
        int rhs = nums.size() - 1;
        if (nums[rhs] < target) return rhs + 1; // 先提前判断一下最右边的数（也就是最大的数）
        while (lhs < rhs) {
            int mid = lhs + (rhs - lhs) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) lhs = mid + 1;
            else rhs = mid;
        }
        return rhs;
    }
};

/* 二分查找
时间复杂度：O(logN)
空间复杂度：O(1)
*/
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target == nums[mid]) return mid;
            if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right + 1;
    }
};

/* 暴力搜索
时间复杂度：O(N)
空间复杂度：O(1)
*/
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int res{0};
        for (const int& num : nums) {
            if (num >= target) return res;
            ++res;
        }
        return res;
    }
};